7945. Гномики
Давным-давно в Гномляндии разгорелась
ожесточённая дискуссия. Правительство планировало ввести удостоверения личности
для всех жителей.
Большинство гномов согласились с тем,
что они маленькие, но категорически не хотели, чтобы их измеряли. В ответ на
эти возражения правительство разрешило заменить в удостоверении личности поле
"высота гнома" на поле "относительная высота гнома". Для
оформления удостоверений у гномов брали интервью, в которых они высказывались о
своём относительном росте. Однако по неизвестной причине правительство
заподозрило, что как минимум один из гномов мог солгать.
Сможете ли вы определить, допускает
ли предоставленная информация возможность того, что хотя бы один из гномов
сказал неправду?
Вход. Первая строка содержит количество
утверждений n (1
≤ n ≤ 105).
Следующие n строк
описывают отношения между гномами. Каждое утверждение задано строкой вида “s1 < s2” или “s1 > s2”, что означает: гном s1 ниже или выше гнома s2 соответственно.
Здесь s1 и s2 –
различные имена гномов.
Имя гнома состоит не более чем
из 20 букв латинского алфавита (заглавных “A” – “Z” и строчных “a” –
“z”). Пробелы в именах не допускаются.
Общее число различных гномов не превышает 104.
Выход. Выведите “impossible”, если утверждения противоречат друг
другу, иначе выведите “possible”.
|
Пример входа 1 |
Пример выхода 1 |
|
3 Dori > Balin Balin > Kili Dori < Kili |
impossible |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
3 Dori > Balin Balin > Kili Dori > Kili |
possible |
РЕШЕНИЕ
графы - циклы
Анализ алгоритма
Построим
ориентированный граф, в котором вершины соответствуют именам карликов. Для
этого каждому имени сопоставим некоторое целое число. Если в утверждении
говорится, что карлик s1
ниже карлика s2 (то есть s1 < s2), то добавим ориентированное ребро из вершины s1 в вершину s2.
Набор
утверждений считается несовместимым, если построенный граф содержит циклы.
Ориентированный граф содержит цикл, если при выполнении поиска в глубину
обнаруживается ребро, ведущее в вершину, которая уже находится в процессе
обработки (так называемую “серую” вершину).
Пример
Графы,
соответствующие приведённым в условии примерам, имеют следующий вид:
Первый
граф содержит цикл, поэтому заданные отношения между карликами противоречивы и
не могут быть истинными одновременно.
Рассмотрим построение графа для первого теста. Первым встречается имя Dori. Присвоим ему номер: m[Dori] = 1. Далее встречается Balin. Установим m[Balin] = 2. Во втором утверждении первым идет Balin. Однако ему уже было присвоено значение, поэтому ничего не
меняем. Следующим идёт Kili. Установим m[Kili] = 3.
Реализация алгоритма
Ориентировнный граф храним в виде списка смежности g. Для обхода в глубину используем
массив used, который отмечает состояние вершин. Соответствие между
именами гномов и номерами вершин сохраняется в отображении name_to_id – гному
с именем s соответствует вершина с номером name_to_id[s].
vector<vector<int>
> g;
vector<int> used;
unordered_map<string, int> name_to_id;
Функция get_id назначает уникальный целочисленный идентификатор имени гнома.
Идентификаторы нуммеруются с 0 до id (не включая id).
int get_id(string name)
{
Если гном с именем name уже
встречался, функция возвращает соответствующий ему идентификатор.
if (name_to_id.count(name)) return name_to_id[name];
В противном случае гному с именем name
присваивается текущий идентификатор id, после чего значение id
увеличивается на 1.
return name_to_id[name] = id++;
}
Функция dfs реализует обход графа в глубину, начиная с вершины v.
void dfs(int v)
{
used[v] = 1;
for (int to : g[v])
{
Ребро (v, to) является текущим рассматриваемым.
Если оно ведет в серую вершину, значит обнаружен цикл, устанавливаем flag = 1.
if (used[to] == 1)
{
flag = 1;
return;
}
Если вершина v еще не посещена,
продолжаем из нее поиск в глубину.
if (used[to] == 0) dfs(to);
}
После завершения обработки всех сыновей вершина v
становится чёрной.
used[v] = 2;
}
Основная часть программы. Читаем количество утверждений
n о соотношении между гномами. Так как общее количество различных гномов не превышает 104, число вершин в графе также не превышает 104.
cin >> n;
g.resize(10001); used.resize(10001,0);
Нумерация гномов начинается с 0.
id = 0;
Обрабатываем n утверждений. Для каждого утверждения строим
ориентированное ребро в графе.
for (i = 0; i < n; i++)
{
Читаем отношение вида s1 < s2
или s1 > s2.
cin >> l >> op >> r;
Каждому имени гнома поставим в соответствие уникальный числовой
идентификатор – номер вершины в графе.
u = get_id(l);
v = get_id(r);
Строим ориентированное ребро графа.
if (op == "<")
g[u].push_back(v);
else
g[v].push_back(u);
}
flag = 0
означает, что в графе нет циклов.
flag = 0;
Запускам поиск в глубину на ориентированном графе.
Вершины графа пронумерованы числами от 0 до id – 1.
for (i = 0; i < id; i++)
{
if (!used[i]) dfs(i);
if (flag == 1) break;
}
В зависимости от значения переменной flag выводм ответ.
if (flag == 1) printf("impossible\n");
else printf("possible\n");
Java реализация
import java.util.*;
public class Main {
static List<List<Integer>> g = new ArrayList<>();
static int[] used;
static Map<String, Integer> nameToId = new HashMap<>();
static int id = 0;
static boolean hasCycle = false;
static int getId(String name) {
if (!nameToId.containsKey(name))
nameToId.put(name, id++);
return nameToId.get(name);
}
static void dfs(int v) {
used[v] = 1;
for (int to : g.get(v)) {
if (used[to] == 1) {
hasCycle = true;
return;
}
if (used[to] == 0) dfs(to);
}
used[v] = 2;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
used = new int[10001];
for (int i = 0; i < 10001; i++)
g.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
String l = sc.next();
String op = sc.next();
String r = sc.next();
int u = getId(l);
int v = getId(r);
if (op.equals("<"))
g.get(u).add(v);
else
g.get(v).add(u);
}
for (int i = 0; i < id; i++) {
if (used[i] == 0) {
dfs(i);
if (hasCycle) break;
}
}
System.out.println(hasCycle ? "impossible" : "possible");
}
}